Title: Rounding Techniques in Approximation Algorithms

Q: Definition of Approximation Algorithm
A: An \(\alpha\)-approximation for an optimization problem is a polynomial time algorithm which produces a solution of cost within a factor of \(\alpha\) of the optimal solution for every instance.

Q: Integer Linear Program and Linear Program Relaxation
A: An Integer Linear Program (ILP) minimizes a linear objective function over a convex polyhedron \(P\). The variables are constrained to be integers. \[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{Z}_{\ge 0}^n
\end{align*}\]If we instead only constrain the variables to be real numbers, we get a Linear Program (LP):\[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{R}_{\ge 0}^n
\end{align*}\]Note we can flip min to max by negating the entries of \(c\), so these programs are fully general.

Q: Integrality Gap
A: The integrality gap of an ILP and its associated LP is the worst case ratio between the ILP OPT and the LP OPT over all instances.

Q: Ellipsoid method and separation oracle
A: Let \(P\) be a convex set. A separation oracle for \(P\) is a polynomial time procedure that given a point \(x \in \mathbb{R}^n\), either certifies that \(x \in P\) or returns a hyperplane that separates \(x\) from \(P\). In other words, it returns a a vector \(a \in \mathbb{R}^n\) such that \(a^Tx > a^Ty\) for all \(y \in P\).
The ellipsoid method is a polynomial time algorithm that can optimize over any convex set with a separation oracle. (In other words, it can solve any LP whose feasible region is convex and has a separation oracle.)
In this course, \(P\) will typically be a convex polyhedron defined by a (possibly exponential size) collection of hyperplanes, and our separation oracle will return one of these hyperplanes.

Q: Relax and round framework
A: Start with an ILP with a separation oracle whose feasible solutions are the feasible solutions for your optimization problem. Then, relax it to an LP, which is polynomial time solvable by the ellipsoid method. After solving this LP, round the resulting solution to a feasible integer solution.

Q: Polyhedron and polytope
A: A polyhedron is the intersection of a finite number of halfspaces. A polytope is a bounded polyhedron.

Q: Threshold rounding
A: The simplest kind of LP rounding. Given an LP solution, round all variables above a certain threshold to their ceiling.
This works for "covering" problems like Vertex Cover in which the constraints are of the form \(a^Tx \ge b\) for \(a \in \mathbb{R}_{\ge 0}^n, b \in \mathbb{R}\).

Q: Union Bound
A: Given \(n\) events \(B_1,\dots,B_n\), the probability any of the events \(B_i\) occur is at most \(\sum_{i=1}^n \mathbb{P}[B_i]\).
In its typical usage, we want to avoid all of the events \(B_i\) with some probability. The union bound says that with probability at least \(1-\sum_{i=1}^n \mathbb{P}[B_i]\), none of the events occur.

Q: Chernoff Bound Lower Tail
A: Let \(X_1,\dots,X_n\) be independent Bernoulli random variables. Then if \(X = \sum_{i=1}^n X_i\), \(L \le \mathbb{E}[X]\), and \(0 \le \delta \le 1\), we have:\[\mathbb{P}[X \le (1-\delta)L] \le \exp(-L\delta^2/2)\]

Q: Chernoff Bound Upper Tails
A: Let \(X_1,\dots,X_n\) be independent Bernoulli random variables. Let \(X = \sum_{i=1}^n X_i\), \(\mathbb{E}[X] \le U\). For small \(\delta >0\), one can use\[\mathbb{P}[X \ge (1+\delta)U] \le \exp(-U\delta^2/(2+\delta))\]When \(\delta \le 1\), often you will see \(\exp(-U\delta^2/3)\). For large \(\delta \ge 2\), the following is stronger: \[\mathbb{P}[X \ge (1+\delta)U] \le \exp(-U\delta \ln \delta/4)\]If you prefer to just remember one bound that can be used to obtain both of these, you can use this for all \(\delta > 0\):\[\mathbb{P}[X \ge (1+\delta)U] < \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^U\]In practice it is just slightly more cumbersome to use. On the quiz, either remember the two bounds for differing values of delta or remember the last bound.

Q: Independent Randomized Rounding
A: In independent randomized rounding, we treat a variable \(x_i\) as a probability. Typically, we will have each \(x_i \in [0,1]\) and we round each variable independently \(i\) to 1 with probability \(x_i\).
This method is used in a straightforward manner for Set Cover (Homework 1) and Karger's argument for \(k\)-edge-connectivity. For the min-congestion multi-commodity flow problem, we treat the paths for each commodity as an independent distribution, but (in a slight twist of this framework) ensure we pick exactly one path. This allows us to ensure we get a feasible solution with probability 1 but still apply Chernoff / Union bounds.

Q: Definition of a vertex of a polyhedron and of an extreme point solution
A: A  vertex of a polyhedron \(P\) is a point \(x\) for which these exists no non-zero direction \(d\) such that \(x+d \in P\) and \(x-d \in P\).
Given an LP over a polyhedron \(P\), an extreme point solution is a vertex of \(P\). As long as the optimal solution to this LP is bounded, there is guaranteed to be an optimal solution which is a vertex. This can be proved using Carathéodory's theorem.

Q: Carathéodory's Theorem
A: If \(x \in \mathbb{R}^n\) is a point in a polytope \(P\), then we can write \(x\) as a convex combination of at most \(n+1\) vertices \(v_1,\dots,v_{n+1}\) of \(P\).
In other words, we have \(x = \sum_{i=1}^{n+1} \lambda_i v_i\) where \(\sum_{i=1}^n \lambda_i = 1\) and \(\lambda_i \ge 0\) for all \(i\).

Q: An inequality for \(e\)
A: \(1-x \le e^{-x}\) for all \(x \in \mathbb{R}\), positive or negative
In general remember \(e^x = 1+x+x^2/2!+x^3/3!+\dots\) by Maclaurin series. So for small \(|x|\), we have \(e^x \approx 1+x\).

Q: 4-color theorem
A: The vertices of a planar graph can be 4-colored. Furthermore, this can be done in polynomial time.

Q: Asymptotics of \(H_n\), the Harmonic Series
A: \(H_n = \sum_{k=1}^n \frac{1}{k}\). As \(n \to \infty\), we have \(H_n = (1+o(1))\ln(n)\).

Q: \(\alpha\)-near minimum cuts and Karger's bound on their number
A: Given a \(k\)-edge-connected graph, a cut is \(\alpha\)-near minimum if it has at most \(\alpha k\) edges. Karger's bound shows there are at most \(n^{2\alpha}\) \(\alpha\)-near minimum cuts.

Q: Nash Williams Theorem
A: Every \(k\)-edge-connected graph contains \(k/2\) edge disjoint spanning trees.

Q: Negative correlation
A: Bernoulli random variables \(X_1,\dots,X_n\) are negatively correlated if for all \(S \subseteq [n]\), we have\[\mathbb{E}[\prod_{i \in S} X_i] \le \prod_{i \in S} \mathbb{E}[X_i]\]Negative correlation implies the Chernoff bound upper tail
They have the negative cylinder property if they are both negatively correlated and 0-negatively correlated.

Q: 0-negative correlation
A: Bernoulli random variables \(X_1,\dots,X_n\) are 0-negatively correlated if for all \(S \subseteq [n]\), we have\[\mathbb{E}[\prod_{i \in S}(1-X_i)] \le \prod_{i \in S} \mathbb{E}[1-X_i]\]0-negative correlation implies the Chernoff bound lower tail

Q: Randomized pipage rounding
A: Given a point \(x\) in a matroid base polytope \(P_M\) with at least one fractional coordinate, randomized pipage rounding finds a direction \(d\) with two non-zero coordinates and an \(\epsilon,\delta >0\) such that \(x+\epsilon d \in P_M\) and \(x-\delta d \in P_M\) and both new points have more tight constraints than \(x\). We move randomly to one of the two points so that the expected movement is 0, and the process is iterated until an integral point is found.
This procedure produces a distribution over bases which is negatively correlated and 0-negatively correlated.

Q: Spanning tree polytope
A: Given a graph \(G=(V,E)\), the spanning tree polytope is the convex hull of all spanning trees. We proved that it is also equal to the following formulation: the set of points \(x \in \mathbb{R}^n\) such that \[\begin{align*} \sum_{e \in E}x_e = |V| -1\\ \sum_{e \in E(S)} x_e \le |S|-1 && \forall S \subseteq V\\ x_e \ge 0 && \forall e \in E \end{align*}\]

Q: Thin Trees and the Thin Tree Conjecture
A: Given a \(k\)-edge-connected graph, a spanning tree \(T\) is \(\alpha\)-thin if for every cut \(S \subseteq V\) we have\[|\delta_T(S)| \le \alpha \cdot |\delta(S)|\]The strong thin tree conjecture is that a tree always exists with \(\alpha \in O(1/k)\). The thin tree conjecture simply asks if for large enough \(k\) we can pick \(\alpha = 0.99\). Both conjectures are wide open.
Given a fractional point \(x\), a spanning tree \(T\) is \(\alpha\)-thin for \(x\) if for every cut \(S \subseteq V\) we have\[|\delta_T(S)| \le \alpha \cdot x(\delta(S))\]To prove the strong thin tree conjecture, it is sufficient to show that we can always find a tree with \(\alpha \in O(1)\) for \(x \in P^\uparrow_{st}\), the dominant of the spanning tree polytope.

Q: Splitting Off
A: Given a multi-graph \(G=(V,E)\), the splitting off theorem states that for any vertex \(u \in V\) of even degree \(2k\), if \(u\) is not incident to any cut edge (an edge whose removal would disconnect the graph), the edges \(uv\) adjacent to \(u\) can be paired up into groups \((ua_1,ub_1),(ua_2,ub_2),\dots,(ua_k,ub_k)\) such that after removing all the edges adjacent to \(u\) and adding edges \(\{a_i,b_i\}\) for all \(i\) the pairwise connectivities \(a,b\) for any vertices \(a,b \not= u\) do not decrease.
This can be used to show that given a fractional graph, we can fully split off any vertex \(v\) to obtain a new fractional graph on \(V \setminus \{v\}\) with the same pairwise connectivities between all vertices \(s,t \not= v\).

Q: Hoffman's Circulation Theorem
A: Let \(G=(V,A)\) be a directed graph. A flow \(f:A \to \mathbb{R}_{\ge 0}\) is a called a circulation if it has equal in and out degree at every vertex.
Hoffman's circulation theorem says that given two flows \(f^l,f^r\), there is an circulation \(r\) with \(f^l_a \le r_a \le f^r_a\) for all \(a \in A\) if and only if \(f^u-f^l \in \mathbb{R}^A_{\ge 0}\) and for all \(S \subset V\), \(f^l(\delta^-(S)) \le f^u(\delta^+(S))\). Remember \(\delta^-(S)\) is the set of edges entering a cut \(S\) and \(\delta^+(S)\) the set of edges leaving.
Finally (and crucially), if \(f^l,f^r\) are integer valued, we can choose \(r\) to be integer valued. This can be proved by showing that the extreme points of the circulation polytope are integral whenever the lower and upper bounds are integral.

Q: Supporting hyperplane
A: A hyperplane \(\{x \in \mathbb{R}^n \mid a^Tx = b\}\) is a supporting hyperplane of a polyhedron \(P\) if \(P\) is fully contained on one side of it

Q: Face, vertex, edge, and facet of a polyhedron
A: A face of a polyhedron \(P\) is the polyhedron itself or its intersection with any supporting hyperplane.
A vertex is a 0-dimensional face and an edge is a 1-dimensional face. A facet is an \(n-1\) dimensional face.

Q: Three equivalent characterizations of a vertex
A: Given a point \(y \in P\) for a polyhedron \(P = \{x \in \mathbb{R}^n \mid Ax \ge b\) for \(A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m\), the following three things are equivalent:
1. \(y\) is a vertex of \(P\)
2. \(y\) is an extreme point of \(P\)
3. There is a subsystem \(\tilde{A},\tilde{b}\) of \(n\) linearly independent constraints (among those defining \(P\)) such that \(y\) is the unique solution to \(\tilde{A}x = \tilde{b}\).

Q: The Rank Lemma
A: Let \(x\) be a vertex of a polyhedron with constraints \(0 \le x_i \le 1\) for all \(i\). Then the number of fractional variables is equal to the maximal number of linearly independent tight non-trivial constraints at \(x\).

Q: Iterative rounding
A: To apply iterative rounding, given a covering problem, we first prove that at any vertex there always exists a variable \(i\) with \(\alpha \le x_i < 1\).
Then, by iteratively rounding up such a variable to 1 and re-solving, we can achieve a \(\frac{1}{\alpha}\) approximation,

Q: Uncrossing
A: Taking a collection of tight constraints and showing that a "simple" subfamily spans all the tight constraints. For a graph with constraints corresponding to cuts, this simple family is typically a laminar family. For a matroid, this is typically a chain, i.e. sets of elements \(E_1 \subseteq E_2 \subseteq \dots \subseteq E\).

Q: Iterative relaxation
A: Consider any linear program and an extreme point solution \(x\). Fix all integer coordinates
of \(x\), delete at least one of the constraints (in some problem-specific manner), and re-solve. Iterate
until all coordinates are integral.